package leetCode;

public class AlphabetBoardPath {
    boolean[][] board = {{true, true, true, true, true}, {true, true, true, true, true}, {true, true, true, true, true},
            {true, true, true, true, true}, {true, true, true, true, true}, {true, false, false, false, false}};

    public String alphabetBoardPath(String target) {
        StringBuilder stringBuilder = new StringBuilder();
        int[] lastPos = {0, 0};
        for (char ch : target.toCharArray()) {
            int[] newPos = getPos(ch);
            getPath(stringBuilder, lastPos, newPos);
            getPath(stringBuilder, lastPos, newPos);
            stringBuilder.append('!');
            lastPos = newPos;
        }
        return stringBuilder.toString();
    }

    private void getPath(StringBuilder stringBuilder, int[] lastPos, int[] newPos) {
        if (lastPos[0] < newPos[0]) {
            while (lastPos[0] < newPos[0] &&isValid(lastPos[0]+1,lastPos[1])){
                lastPos[0]++;
                stringBuilder.append('D');
            }
        }else if(lastPos[0]>newPos[0]){
            while (lastPos[0]> newPos[0] && isValid(lastPos[0]-1,lastPos[1])){
                lastPos[0]--;
                stringBuilder.append('U');
            }
        }
        if(lastPos[1]<newPos[1]){
            while (lastPos[1] < newPos[1] && isValid(lastPos[0],lastPos[1]+1)){
                lastPos[1]++;
                stringBuilder.append('R');
            }
        }else if(lastPos[1]>newPos[1]) {
            while (lastPos[1] > newPos[1] && isValid(lastPos[0],lastPos[1]-1)) {
                lastPos[1]--;
                stringBuilder.append('L');
            }
        }
    }

    private boolean isValid(int x, int y) {
        if(x<0||x>5||y<0||y>4){
            return false;
        }
        if(x==5){
            return y==0;
        }
        return true;
    }



    private int[] getPos(char ch) {
        int diff = ch - 'a';
        return new int[]{diff / 5, diff % 5};
    }

    public static void main(String[] args){
        new AlphabetBoardPath().alphabetBoardPath("cz");
    }
}
